Хроматичне число

Розфарбовування графа Петерсена у 3 кольори.

Хроматичне число графа G — мінімальна кількість кольорів, в які можна розфарбувати вершини графа G таким чином, щоб кінці будь-якого ребра мали різні кольори. Позначається як χ(G).

Визначення

Хроматичне число графа — мінімальне число $k$, таке що множину $V$ вершин графа можна розбити на $k$ класів $C_{1},C_{2},\ldots ,C_{k}$, що не перетинаються:

$V=\bigcup _{i}^{}C_{i};\ C_{i}\cap C_{j}=\varnothing ,$

таких, що вершини в кожному класі незалежні, тобто будь-яке ребро графа не з'єднує вершини одного й того ж класу.

Пов'язані визначення

• K-розфарбовний граф — граф, хроматичне число якого не перевищує $K$. Тобто його вершини можна розфарбувати $K$ різними кольорами так, що кінці будь-якого ребра будуть різних кольорів.
• K-хроматичний граф — граф, хроматичне число якого дорівнює $K$.

Реброве розфарбування

Реброве розфарбування кубічного графа

Хроматичний клас графа G — мінімальна кількість кольорів , в які можна розфарбувати ребра графа G так, щоб суміжні ребра були різних кольорів. Позначається χ'(G). Проблема ребрового розфарбування довільного плаского кубічного графа без мостів трьома кольорами еквівалентна відомій Проблемі чотирьох фарб. Реброве розфарбування визначає 1-факторизацію графа.

Хроматичний многочлен

Цей граф може бути розфарбувати у 3 кольори 12-ма способами.

Якщо розглядати кількість відмінних розфарбувань позначеного графа як функцію від доступної кількості кольорів t, то з'ясується, що ця функція завжди буде поліномом від t. Цей факт був виявлений Біркгофом і Д. С. Люїсом-мол. при спробі довести гіпотезу чотирьох фарб.

Розглянемо граф, зображений на малюнку. Використовуючи лише три кольори, існує 12 варіантів розфарбування. З двома кольорами його взагалі не можна розфарбувати. З чотирма, він може бути розфарбований у 24 + 4*12 = 72 спосіб: використання всіх чотирьох дає 4! = 24 правильних розфарбувань; і для кожного вибору 3-х з 4-х доступних кольорів маємо 12 варіантів. Таким чином, таблиця кількості правильних розфарбувань виглядає таким чином:

Доступно кольорів	1	2	3	4	…
Кількість розфарбувань	0	0	12	72	…

Хроматичний многочлен — функція P(G, t), яка рахує кількість t-розфарбувань G. Для графа з малюнка P(G, t) = t(t − 1)²(t − 2), і насправді, P(G, 4) = 72.

Хроматичні многочлени деяких графів

Трикутник $K_{3}$	$t(t-1)(t-2)$
Повний граф $K_{n}$	$t(t-1)(t-2)...(t-(n-1))$
Дерево с $n$ вершинами	$t(t-1)^{n-1}$
Цикл $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
Граф Петерсена	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$

Узагальнення

Також хроматичне число можна розглядати для інших об'єктів, наприклад, для метричних просторів. Так хроматичним числом площини називається мінімальне число χ таке, що існує розфарбування всіх точок площини в один із χ кольорів і при цьому ніякі дві точки одного кольору не розташовані на відстані 1 одна від одної (площина не містить монохроматичних відрізків довжини 1). Аналогічно для простору будь-якої розмірності.

Значення для теорії графів

Багато глибоких задач теорії графів легко формулюються в термінах розфарбовування. Найвідоміша з-посеред таких задач, проблема чотирьох фарб, на сьогодні розв'язана, однак з'являються нові, наприклад, узагальнення проблеми чотирьох фарб, гіпотеза Хадвігера.

Див. також

• Хроматичний індекс
• Критичний граф
• Дробове розфарбування